package Common;

import java.util.Iterator;
import java.util.Vector;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.Set;
import java.io.*;

/**
 * Represents a pattern.
 *
 */
public class Pattern {

	// The non-optional search pattern
	private String[] pattern;
	// The non-optional search pattern with markers designating the position of parenthesis
	private String[] patternWithMarkers;

	// Is the pattern a regular expression
	private boolean regExp;

	// Symbol to position for non-optional symbols
	private HashMap<String, ArrayList<Integer>> symbolToPosition;
	// Symbol to position for optional symbols
	private HashMap<String, ArrayList<Integer>> symbolToPositionOptional;

	// Groups of optional symbols
	private Vector<Vector<String>> optionalSymbolGroups;

	/**
	 * Get a grouping of symbols within parenthesis
	 *
	 * @param the optional symbol group to get
	 * @return the optional symbol group
	 */
	public Vector<String> getOptSymbolGroup(int i) {
		return optionalSymbolGroups.elementAt(i);
	}

	/**
	 * Gets the pattern as an array
	 *
	 * @return Pattern as array of strings
	 */
	public String[] pattern() {

		return this.pattern;
	}

	/**
	 * Find the number of symbols in the non-optional pattern
	 *
	 * @return the length of the pattern
	 */
	public int length() {

		return this.pattern.length;
	}

	/**
	 * Find the number of symbols in the non-optional pattern with markers
	 *
	 * @return the length of the non-optional pattern + markers
	 */
	public int lengthWithMarkers() {
		return this.patternWithMarkers.length;
	}

	/**
	 * Find the number of symbols in the optional pattern
	 *
	 * @return the length of the optional pattern
	 */
	public int optLength() {
		int length = 0;
		// Find a set of symbols that can be optionally matched
		Set<String> patternSymbolSet = this.symbolToPositionOptional.keySet();
		Iterator<String> si = patternSymbolSet.iterator();
		while(si.hasNext()) {
			length += this.symbolToPositionOptional.get(si.next()).size();
		}
		return length;
	}

	/**
	 * Does the given symbol appear within the pattern
	 *
	 * @param symbol the symbol to look for within the pattern
	 * @return True if symbol is in pattern - otherwise false
	 */
	public boolean contains(String symbol) {

		return symbolToPosition.containsKey(symbol);
	}

	/**
	 * Find a set of non-optional symbols in the pattern
	 *
	 * @return a Set of the unique symbols in the pattern
	 */
	public Set<String> symbolSet() {
		return this.symbolToPosition.keySet();
	}

	/**
	 * Retrieve a symbol at a given index in the pattern
	 *
	 * @param i the pattern index to retrieve the symbol
	 * @return the symbol at the given index
	 */
	public String elementAt(int i) {
		return this.pattern[i];
	}

	/**
	 * Retrieve a symbol at a given index in the patter with markers
	 *
	 * @param i the pattern index to retrieve the symbol
	 * @return the symbol at the given index
	 */
	public String elementAtWithMarkers(int i) {
		return this.patternWithMarkers[i];
	}

	/**
	 * Convert the pattern into a string
	 *
	 * @return a string of the pattern
	 */
	public String toString() {
		StringBuilder sb = new StringBuilder();
		if (!this.regExp) {
			sb.append("[");
			for (int i = 0; i < this.pattern.length; i++) {
				sb.append(this.pattern[i]);
				if (i != this.pattern.length-1)
					sb.append(", ");
			}
			sb.append("]");
		}
		else {
			int optGrpCnt = 0;
			for (int i = 0; i < this.patternWithMarkers.length; i++) {
				if (this.patternWithMarkers[i].equals("*")) {
					sb.append("(");
					for (int j = 0; j < this.optionalSymbolGroups.get(optGrpCnt).size(); j++) {
						sb.append(this.optionalSymbolGroups.get(optGrpCnt).get(j));
						if (j == this.optionalSymbolGroups.get(optGrpCnt).size()-1)
							sb.append(")");
					}
					optGrpCnt++;
				}
				sb.append(this.patternWithMarkers[i]);
			}
		}
		return sb.toString();
	}

	/**
	 * Is the pattern a regular expressions
	 *
	 * @return True the pattern is a regular expression - False otherwise
	 */
	public boolean isRegExp() {
		return this.regExp;
	}

	/**
	 * Assert the pattern belongs to the alphabet
	 * and if a regular expression contains only the special character '(',')','*'
	 *
	 * @param alpha the alphabet
	 * @param pattern to validate
	 * @return True the pattern is valid - False otherwise
	 */
	private boolean validPattern(String[] alpha, String[] pattern) {

		StringBuilder alphaRegExp = new StringBuilder();
		StringBuilder searchPat = new StringBuilder();

		// Create the alphabet regular expression
		alphaRegExp.append("[");
		for (int i = 0; i < alpha.length; i++) {
			alphaRegExp.append(alpha[i]);
		}
		alphaRegExp.append("\\(\\)\\*]+");

		// Convert the search pattern to a string
		for (int i = 0; i < pattern.length; i++) {
			searchPat.append(pattern[i]);
		}

		// Determine whether the pattern is a regular expression
		this.regExp = java.util.regex.Pattern.matches(".*[\\(]{1}.+[\\)]{1}[\\*]{1}.*", searchPat.toString());

		// Determine whether the pattern is valid
		java.util.regex.Pattern p = java.util.regex.Pattern.compile(alphaRegExp.toString());
		java.util.regex.Matcher m = p.matcher(searchPat.toString());
		return m.matches();
	}

	/**
	 * Pattern constructor
	 *
	 * @param alpha the alphabet
	 * @param pattern the pattern
	 * @throws Exception when the pattern is not a sub-set of the alphabet
	 */
	public Pattern(String[] alpha, String[] pattern) throws Exception {

		// Assert the pattern is valid
		if (validPattern(alpha, pattern)) {

			if (!regExp) {

				// Initialise the pattern array
				this.pattern = pattern;
				// Instantiate the pattern hashMap, where the key is the pattern
				// and the value is its position in the pattern
				symbolToPosition = new HashMap<String, ArrayList<Integer>>();

				// Initialise the pattern hashMap
				for (int i = 0; i < pattern.length; i++) {

					// Instantiate the list of positions
					ArrayList<Integer> list = new ArrayList<Integer>();

					if (!pattern[i].equals("(") && !pattern[i].equals(")") && !pattern[i].equals("*")) {
						// Test if the pattern is a repeat
						if (symbolToPosition.containsKey(pattern[i])){
							// Find the list of previous positions this pattern has been found
							list.addAll(symbolToPosition.get(pattern[i]));
							// Add this position to the end of the list
							list.add(Integer.valueOf(i));
						}
						else {
							// Add this position to a new list, this is the first time this
							// pattern has been found
							list.add(Integer.valueOf(i));
						}
					}
					else {
						Exception e = new Exception("Invalid regular expression");
						throw e;
					}

					// Create a mapping from this pattern to the list of positions its been found
					symbolToPosition.put(pattern[i], list);
				}
			}
			else {
				Vector<String> pat = new Vector<String>();
				Vector<String> patWithMarkers = new Vector<String>();
				Vector<String> patOpt = new Vector<String>();
				// The pattern is a regular expression
				symbolToPosition = new HashMap<String, ArrayList<Integer>>();
				symbolToPositionOptional = new HashMap<String, ArrayList<Integer>>();
				optionalSymbolGroups = new Vector<Vector<String>>();
				// Characters found within brackets are optional
				boolean optional = false;
				for (int i = 0; i < pattern.length; i++) {
					ArrayList<Integer> list = new ArrayList<Integer>();

					// Determine the whether the symbols is within brackets or not
					if (pattern[i].equals("(")) {
						optional = true;
					}
					else {
						if (pattern[i].equals(")")) {
							optional = false;
						}
						else {
							if (!optional) {
								// "*" used as a marked of optional groups
								if (pattern[i].equals("*")) {
									// Assign the optional symbol group to the vector of optional symbols
									if (!patOpt.isEmpty()) {
										optionalSymbolGroups.add(new Vector<String>(patOpt));
										patOpt.clear();
									}
								}
								else {
									// The symbols is outside of brackets
									if (symbolToPosition.containsKey(pattern[i])){
										list.addAll(symbolToPosition.get(pattern[i]));
										list.add(Integer.valueOf(i));
									}
									else {
										list.add(Integer.valueOf(i));
									}
									symbolToPosition.put(pattern[i], list);
									pat.add(pattern[i]);
								}
								patWithMarkers.add(pattern[i]);
							}
							else {
								// The symbol is inside brackets
								if (symbolToPositionOptional.containsKey(pattern[i])) {
									list.addAll(symbolToPositionOptional.get(pattern[i]));
									list.add(Integer.valueOf(i));
								}
								else {
									list.add(Integer.valueOf(i));
								}
								symbolToPositionOptional.put(pattern[i], list);
								patOpt.add(pattern[i]);
							}
						}
					}
				}
				this.patternWithMarkers = new String[patWithMarkers.size()];
				patWithMarkers.toArray(this.patternWithMarkers);
				this.pattern = new String[pat.size()];
				pat.toArray(this.pattern);
			}
		}
		else {
			//  The pattern is invalid
			Exception e = new Exception("Patter symbol does not belong to the alphabet");
			throw e;
		}
	}

	/**
	 * Pattern constructor
	 *
	 * @param alpha the alphabet the pattern belongs to
	 * @param filename to read the pattern from
	 * @throws Exception when the pattern is not a sub-set of the alphabet
	 */
	public Pattern(String[] alpha, String filename) throws Exception {

		this(alpha, readFile(filename));
	}

	/**
	 * Reads a pattern from file.
	 *
	 * @param filename The filename to read the pattern from
	 * @return A string array containing the pattern
	 * @throws Exception file exceptions
	 */
	private static String[] readFile(String filename) throws Exception {

		Vector<String> p = new Vector<String>();
		// Open the file for reading
		BufferedReader in = new java.io.BufferedReader(new FileReader(filename));
		String s;
		int n = 0;
		// Read from the file while more lines to read
		do {
			s = in.readLine();
			if (s != null) {
				p.add(s);
				n++;
			}
		} while (s != null);
		in.close();
		// Conversion buffer
		String[] buffer = new String[n];
		// Convert vector to array
		return p.toArray(buffer);
	}
}